package com.c2b.algorithm.leetcode.base;

import java.util.Deque;
import java.util.LinkedList;

/**
 * <a href="https://leetcode.cn/problems/flatten-binary-tree-to-linked-list/">二叉树展开为链表(Flatten Binary Tree to Linked List)</a>
 * <p>给你二叉树的根结点 root ，请你将它展开为一个单链表：
 * <ul>
 * <li>展开后的单链表应该同样使用 TreeNode ，其中 right 子指针指向链表中下一个结点，而左子指针始终为 null 。</li>
 * <li>展开后的单链表应该与二叉树 <a href="https://baike.baidu.com/item/%E5%89%8D%E5%BA%8F%E9%81%8D%E5%8E%86/757319?fromtitle=%E5%85%88%E5%BA%8F%E9%81%8D%E5%8E%86&fromid=6442839">先序遍历</a> 顺序相同。</li>
 * </ul></p>
 * <p>
 *     <b>示例：</b>
 *
 * <pre>
 * 示例 1：
 *      输入：root = [1,2,5,3,4,null,6]        输出：[1,null,2,null,3,null,4,null,5,null,6]
 *                  1                               1
 *                /  \                            /  \
 *               2    5                         null  2
 *              / \    \                             / \
 *             3   4    6                          null 3
 *                                                     / \
 *                                                   null 4
 *                                                       / \
 *                                                     null 5
 *                                                         / \
 *                                                       null 6
 * 示例 2：
 *      输入：root = []
 *      输出：[]
 *
 * 示例 3：
 *      输入：root = [0]
 *      输出：[0]
 * </pre>
 * </p>
 * <p>
 *     <b>提示：</b>
 * <ul>
 * <li>树中结点数在范围 [0, 2000] 内</li>
 * <li>-100 <= Node.val <= 100</li>
 * </ul>
 * </p>
 *
 *
 * <b>进阶：你可以使用原地算法（O(1) 额外空间）展开这棵树吗？</b>
 *
 * @author c2b
 * @see LC0114FlattenBinaryTreeToLinkedList_M 二叉树展开为链表(Flatten Binary Tree to Linked List)
 * @see LC0430FlattenMultilevelDoublyLinkedList_M 扁平化多级双向链表(Flatten a Multilevel Doubly Linked List)
 * @since 2023/4/27 16:09
 */
public class LC0114FlattenBinaryTreeToLinkedList_M {

    static class Solution {

        public void flatten(TreeNode root) {
            /*
             * 思路：
             *      1.如果当前节点左子节点为null，进入右子节点继续判断
             *      2.如果当前节点左子节点非null：
             *          2.1 找到以左子节点为根节点的树中的最右子节点 leftTreeRightmostNode
             *          2.2 让当前节点的右子树成为 leftTreeRightmostNode 的右子节点
             *          2.3 让当前节点的左子树成为右子树
             *          2.4 当前节点的左子树置为 null
             *          2.5 进入右子节点继续判断
             */
            TreeNode currNode = root;
            while (currNode != null) {
                // 如果一个节点的左子节点不为空，则该节点的左子树中的最后一个节点被访问之后，该节点的右子节点被访问。
                // 该节点的左子树中最后一个被访问的节点是左子树中的最右边的节点，也是该节点的前驱节点。
                // 因此，问题转化成寻找当前节点的前驱节点。
                if (currNode.left != null) {
                    // 找到以左子节点为根节点的树中的最右子节点 leftTreeRightmostNode
                    TreeNode nextNodeRightmostNode = currNode.left;
                    while (nextNodeRightmostNode.right != null) {
                        nextNodeRightmostNode = nextNodeRightmostNode.right;
                    }
                    // 将 currNode 的右子树挂到 currNode 的左子树最右子节点上
                    nextNodeRightmostNode.right = currNode.right;
                    currNode.right = currNode.left;
                    currNode.left = null;
                }
                // 如果一个节点的左子节点为空，则该节点不需要进行展开操作
                currNode = currNode.right;
            }
        }

        public void flatten2(TreeNode root) {
            if (root == null) {
                return;
            }
            // 使用辅助栈实现先序遍历：先进后出
            Deque<TreeNode> stack = new LinkedList<>();
            stack.add(root);
            while (!stack.isEmpty()) {
                TreeNode currNode = stack.poll();
                if (currNode.right != null) {
                    stack.add(currNode.right);
                }
                if (currNode.left != null) {
                    stack.add(currNode.left);
                }
                // 让当前节点的左子节点指向null
                currNode.left = null;
                // 让当前节点的右子节点指向栈中的下一个元素
                currNode.right = stack.isEmpty() ? null : stack.peekLast();
            }
        }
    }

    public static void main(String[] args) {
        TreeNode node = new TreeNode(1);
        node.left = new TreeNode(2);
        node.right = new TreeNode(5);
        node.left.left = new TreeNode(3);
        node.left.right = new TreeNode(4);
        node.right.right = new TreeNode(6);
        Solution solution = new Solution();
        solution.flatten(node);
    }
}
